package  main.java.leetcode.editor.cn;
//2022-04-01 13:48:47
//给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i 
//+ 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [3,1,3,6]
//输出：false
// 
//
// 示例 2： 
//
// 
//输入：arr = [2,1,2,6]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：arr = [4,-2,2,-4]
//输出：true
//解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= arr.length <= 3 * 104 
// arr.length 是偶数 
// -105 <= arr[i] <= 105 
// 
// Related Topics 贪心 数组 哈希表 排序 
// 👍 121 👎 0

import java.util.*;

class ArrayOfDoubledPairs {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new ArrayOfDoubledPairs().new Solution();
        int[] test = {10,20,40,80};
        System.out.println(solution.canReorderDoubled(test));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        //对数组内的元素进行计数,
        for(int num : arr){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //如果0的个数为奇数直接退出
        if(map.getOrDefault(0,0)%2 != 0){
            return false;
        }
        //将Map集合中的键取出并排序
        List<Integer> listSort = new LinkedList<>();
        for(int list : map.keySet()){
            listSort.add(list);
        }
        Collections.sort(listSort, (a, b) -> Math.abs(a) - Math.abs(b));
        for(int result : listSort){
            //未找到配对数
            if(map.getOrDefault(2*result,0) < map.get(result)){
                return false;
            }
            map.put(2*result, map.getOrDefault(2*result,0)-map.get(result));
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
